16.1 Матричное дифференцирование

Как дифференцировать матрицы и дифференцировать по матрицам: всё, что вам не рассказали про дифференцирование на матанализе

Любая задача машинного обучения — это задача оптимизации, а задачи оптимизации удобнее всего решать градиентными методами (если это возможно, конечно). Поэтому важно уметь находить производные всего, что попадается под руку. Казалось бы, в чём проблема: ведь дифференцирование — простая и понятная штука (чего не скажешь, например, об интегрировании). Зачем же как-то специально учиться дифференцировать матрицы?

Да в принципе-то никаких проблем: в этом параграфе вы не узнаете никаких секретных приёмов или впечатляющих теорем. Но, согласитесь, если исходная функция от вектора xx имела вид f(x)=Axb2f(x) = \vert\vert Ax - b\vert\vert^2 (где AA — константная матрица, а bb — постоянный вектор), то хотелось бы уметь и производную выражать красиво и цельно через буквы AA, xx и bb, не привлекая отдельные координаты AijA_{ij}, xkx_k и bsb_s. Это не только эстетически приятно, но и благотворно сказывается на производительности наших вычислений: ведь матричные операции обычно очень эффективно оптимизированы в библиотеках, чего не скажешь о самописных циклах по i,j,k,si, j, k, s. И всё, что будет происходить дальше, преследует очень простую цель: научиться вычислять производные в удобном, векторно-матричном виде. А чтобы сделать это и не сойти с ума, мы должны ввести ясную систему обозначений, составляющую ядро техники матричного дифференцирования.

Основные обозначения

Вспомним определение производной для функции f:RmRnf:\mathbb{R}^m\rightarrow\mathbb{R}^n. Функция f(x)f(x) дифференцируема в точке x0x_0, если

f(x0+h)=f(x0)+[Dx0f](h)+oˉˉ(h),f(x_0 + h) = f(x_0) + \color{#348FEA}{\left[D_{x_0} f \right]} (h) + \bar{\bar{o}} \left(\left| \left| h\right|\right|\right),

где [Dx0f]\color{#348FEA}{\big[D_{x_0} f\big]}дифференциал функции ff: линейное отображение из мира xx-ов в мир значений ff. Грубо говоря, он превращает «малое приращение h=Δxh=\Delta x» в «малое приращение Δf\Delta f» («малые» в том смысле, что на о-малое можно плюнуть):

f(x0+h)f(x0)[Dx0f](h)f(x_0 + h) - f(x_0)\approx\color{#348FEA}{\left[D_{x_0} f \right]} (h)

Отметим, что дифференциал зависит от точки x0x_0, в которой он берётся: [Dx0f](h)\color{#348FEA}{\left[D_{\color{red}{x_0}} f \right]} (h). Под h\vert\vert h\vert\vert подразумевается норма вектора hh, например корень из суммы квадратов координат (обычная евклидова длина).

Давайте рассмотрим несколько примеров и заодно разберёмся, какой вид может принимать выражение [Dx0f](h)\color{#348FEA}{\big[D_{x_0} f\big]} (h) в зависимости от формы xx. Начнём со случаев, когда ff — скалярная функция.

Примеры конкретных форм [Dx0f](h)\big[D_{x_0} f\big] (h), когда ff — скалярная функция
  1. f(x)f(x) — скалярная функция, xx — скаляр. Тогда

f(x0+h)f(x0)f(x0)hf(x_0 + h) - f(x_0) \approx f'(x_0) \cdot h

[Dx0f](h)=f(x0)h=hf(x0)\color{#348FEA}{\left[D_{x_0} f\right] (h)} = f'(x_0) h = h \cdot f'(x_0)

Здесь hh и f(x0)f'(x_0) — просто числа. В данном случае [Dx0f]\color{#348FEA}{\left[D_{x_0} f\right]} — это обычная линейная функция.

  1. f(x)f(x) — скалярная функция, xx — вектор. Тогда

f(x0+h)f(x0)ifxix=x0hi,f(x_0 + h) - f(x_0) \approx \sum\limits_i \left.\frac{\partial f}{\partial x_i} \right|_{x=x_0} h_i,

то есть

[Dx0f](h)=(x0f)Th=x0f,h, \color{#348FEA}{\left[D_{x_0} f\right]}(h) = \left(\color{#FFC100}{\nabla_{x_0} f}\right)^T h = \langle\color{#FFC100}{\nabla_{x_0} f}, h \rangle,

где ,\langle\bullet, \bullet\rangle — операция скалярного произведения, а x0f=(fx1,,fxn)\color{#FFC100}{\nabla_{x_0} f} = \left(\frac{\partial f}{\partial x_1}, \ldots, \frac{\partial f}{\partial x_n}\right) — градиент функции ff.

  1. f(x)f(x) — скалярная функция, XX — матрица. Дифференциал скалярной функции по матричному аргументу определяется следующим образом:

f(X0+H)f(X0)i,j fXijX=X0Hij f(X_0 + H) - f(X_0) \approx \sum\limits_{i,j}\ \left.\frac{\partial f}{\partial X_{ij}} \right|_{X=X_0} H_{ij}

Можно заметить, что это стандартное определение дифференциала функции многих переменных для случая, когда переменные — элементы матрицы XX. Заметим также один интересный факт:

ijAijBij=trATB, \sum_{ij} A_{ij} B_{ij} = \text{tr} A^T B,

где AA и BB — произвольные матрицы одинакового размера. Объединяя оба приведённых выше факта, получаем:

[DX0f](H)=ijfXijX=X0(XX0)ij=tr([fXijX=X0]TH). \color{#348FEA}{\left[D_{X_0} f \right]} (H) = \sum \limits_{ij} \left. \frac{\partial f}{\partial X_{ij}} \right|_{X = X_0} \left( X - X_0 \right)_{ij} = \text{tr}\, \left( \left[\left. \frac{\partial f}{\partial X_{ij}}\right|_{X=X_0}\right]^T H\right).

Можно заметить, что здесь, по аналогии с примерами, где xx — скаляр и где xx — вектор (и f(x)f(x) — скалярная функция), получилось на самом деле скалярное произведение градиента функции ff по переменным XijX_{ij} и приращения. Этот градиент мы записали для удобства в виде матрицы с теми же размерами, что матрица XX.

В примерах выше нам дважды пришлось столкнуться с давним знакомцем из матанализа: градиентом скалярной функции (у нескалярных функций градиента не бывает). Напомним, что градиент x0f\color{#FFC100}{\nabla_{x_0} f} функции в точке x0x_0 состоит из частных производных этой функции по всем координатам аргумента. При этом его обычно упаковывают в ту же форму, что и сам аргумент: если xx — вектор-строка, то и градиент записывается вектор-строкой, а если xx — матрица, то и градиент тоже будет матрицей того же размера. Это важно, потому что для осуществления градиентного спуска мы должны уметь прибавлять градиент к точке, в которой он посчитан.

Как мы уже имели возможность убедиться, для градиента скалярной функции ff выполнено равенство

[Dx0f](xx0)=x0f,xx0, \left[D_{x_0} f \right] (x-x_0) = \langle\color{#FFC100}{\nabla_{x_0} f}, x-x_0\rangle,

где скалярное произведение — это сумма попарных произведений соответствующих координат (да-да, самое обыкновенное).

Посмотрим теперь, как выглядит дифференцирование для функций, которые на выходе выдают не скаляр, а что-то более сложное.

Примеры [Dx0f](h)\big[D_{x_0} f\big] (h), где ff — это вектор или матрица

f(x)=(f(x1)f(xm))f(x) = \begin{pmatrix} f(x_1)\\ \vdots\\ f(x_m) \end{pmatrix}

xx — вектор. Тогда

f(x0+h)f(x0)=(f(x01+h1)f(x01)f(x0m+hm)f(x0m))(f(x01)h1f(x0m)hm)=(f(x01)f(x0m))h.f(x_0 + h) - f(x_0) = \begin{pmatrix} f(x_{01} + h_1) - f(x_{01})\\ \vdots \\ f(x_{0m} + h_m) - f(x_{0m}) \end{pmatrix} \approx \begin{pmatrix} f'(x_{01}) h_1\\ \vdots \\ f'(x_{0m}) h_m \end{pmatrix} = \begin{pmatrix} f'(x_{01}) \\ \vdots \\ f'(x_{0m}) \end{pmatrix} \odot h.

В последнем выражении происходит покомпонентное умножение:

[Dx0f](h)=f(x0)h=hf(x0)\color{#348FEA}{\big[D_{x_0} f\big]} (h) = f'(x_0) \odot h = h \odot f'(x_0)

  1. f(X)=XWf(X) = XW, где XX и WW — матрицы. Тогда

f(X0+H)f(X0)=(X0+H)WX0W=HW,f(X_0 + H) - f(X_0) = (X_0 + H) W - X_0 W = H W,

то есть

[DX0f](H)=HW\color{#348FEA}{\big[D_{X_0} f\big]} (H) = H W

  1. f(W)=XWf(W) = XW, где XX и WW — матрицы. Тогда

f(W0+H)f(W0)=X(W0+H)XW0=XH,f(W_0 + H) - f(W_0) = X(W_0 + H) - XW_0 = X H,

то есть

[DW0f](H)=XH\color{#348FEA}{\big[D_{W_0} f\big]} (H) = X H

  1. f(x)=(f1(x),,fK(x))f(x) = (f_1(x),\ldots,f_K(x)) — вектор-строка, x=(x1,,xD)x = (x_1,\ldots,x_D) — вектор-строка. Тогда

[Dx0f](h)=(jf1yjy=x0hj,,jfKyjy=x0hj)=\color{#348FEA}{\big[D_{x_0} f\big]}(h) = \left(\sum_j \left. \frac{\partial f_1}{\partial y_j} \right|_{y=x_0}h_j, \ldots, \sum_j \left. \frac{\partial f_K}{\partial y_j} \right|_{y=x_0}h_j \right) =

=h(f1y1y=x0fky1y=x0f1yDy=x0fkyDy=x0)=hfyy=x0= h \cdot \begin{pmatrix} \left. \frac{\partial f_1}{\partial y_1} \right|_{y=x_0} & \ldots & \left. \frac{\partial f_k}{\partial y_1} \right|_{y=x_0} \\ \vdots & & \vdots \\ \left. \frac{\partial f_1}{\partial y_D} \right|_{y=x_0} & \ldots & \left. \frac{\partial f_k}{\partial y_D} \right|_{y=x_0}\\ \end{pmatrix} = h \cdot \left. \frac{\partial f}{\partial y}\right|_{y = x_0}

Матрица, выписанная в предпоследней выкладке, — это знакомая вам из курса матанализа матрица Якоби.

Простые примеры и свойства матричного дифференцирования

  1. Производная константы. Пусть f(x)=af(x) = a. Тогда

    f(x0+h)f(x0)=0,f(x_0 + h) - f(x_0) = 0,

    то есть [Dx0f]\color{#348FEA}{\big[D_{x_0} f\big]} — это нулевое отображение. А если ff — скалярная функция, то и x0f=0.\color{#FFC100}{\nabla_{x_0} f} = 0.

  2. Производная линейного отображения. Пусть f(x)f(x) — линейное отображение. Тогда

    f(x0+h)f(x0)=f(x0)+f(h)f(x0)=f(h)f(x_0 + h) - f(x_0) = f(x_0) + f(h) - f(x_0) = f(h)

    Поскольку справа линейное отображение, то по определению оно и является дифференциалом [Dx0f]\color{#348FEA}{\big[D_{x_0} f\big]}. Мы уже видели примеры таких ситуаций выше, когда рассматривали отображения умножения на матрицу слева или справа. Если ff — (скалярная) линейная функция, то она представляется в виде a,v\langle a, v\rangle для некоторого вектора aa — он и будет градиентом ff.

  3. Линейность производной. Пусть f(x)=λu(x)+μv(x)f(x) = \lambda u(x) + \mu v(x), где λ,μ\lambda, \mu — скаляры, а u,vu, v — некоторые отображения, тогда

    [Dx0f]=λ[Dx0u]+μ[Dx0v]\color{#348FEA}{\big[D_{x_0} f\big]} = \lambda \color{#348FEA}{\big[D_{x_0} u\big]} + \mu \color{#348FEA}{\big[D_{x_0} v\big]}

Попробуйте доказать сами, прежде чем смотреть доказательство.

f(x0+h)f(x0)=(λu(x0+h)+μv(x0+h))(λu(x0)+μv(x0))=f(x_0 + h) - f(x_0) = (\lambda u(x_0 + h) + \mu v(x_0 + h)) - (\lambda u(x_0) + \mu v(x_0)) =

=λ(u(x0+h)u(x0))+μ(v(x0+h)v(x0))= \lambda(u(x_0 + h) - u(x_0)) + \mu(v(x_0 + h) - v(x_0)) \approx

λ[Dx0u](h)+μ[Dx0v](h)\approx \lambda \color{#348FEA}{\big[D_{x_0} u\big]}(h) + \mu \color{#348FEA}{\big[D_{x_0} v\big]}(h)

  1. Производная произведения. Пусть f(x)=u(x)v(x)f(x) = u(x) v(x), где u,vu, v — некоторые отображения, тогда

    [Dx0f]=[Dx0u]v(x0)+u(x0)[Dx0v]\color{#348FEA}{\big[D_{x_0} f\big]} = \color{#348FEA}{\big[D_{x_0} u\big]} \cdot v(x_0) + u(x_0) \cdot \color{#348FEA}{\big[D_{x_0} v\big]}

Попробуйте доказать сами, прежде чем смотреть доказательство.

Обозначим для краткости x=x0+hx = x_0 + h. Тогда

u(x)v(x)u(x0)v(x0)=u(x)v(x)u(x0)v(x)+u(x0)v(x)u(x0)v(x0)=u(x)v(x) - u(x_0)v(x_0) = u(x)v(x) - u(x_0)v(x) + u(x_0)v(x) - u(x_0)v(x_0) =

(u(x)u(x0))v(x)+u(x0)(v(x)v(x0))(u(x) - u(x_0))v(x) + u(x_0)(v(x) - v(x_0))\approx

[Dx0u](h)v(x)+u(x0)[Dx0v](h)\approx \color{#348FEA}{\big[D_{x_0} u\big]}(h) \cdot v(x) + u(x_0)\cdot \color{#348FEA}{\big[D_{x_0} v\big]}(h)

И всё бы хорошо, да в первом слагаемом v(x)v(x) вместо v(x0)v(x_0). Придётся разложить ещё разок:

[Dx0u](h)v(x)\color{#348FEA}{\big[D_{x_0} u\big]}(h) \cdot v(x) \approx

[Dx0u](h)(v(x0)+[Dx0v](h)+o(h))=\color{#348FEA}{\big[D_{x_0} u\big]}(h) \cdot \left(v(x_0) + \color{#348FEA}{\big[D_{x_0} v\big]}(h) + o(\vert\vert h\vert\vert)\right) =

[Dx0u](h)v(x0)+oˉˉ(h)\color{#348FEA}{\big[D_{x_0} u\big]}(h) \cdot v(x_0) + \bar{\bar{o}}\left(\vert\vert h\vert\vert\right)

Это же правило сработает и для скалярного произведения:

[Dx0u,v]=[Dx0u],v+u,[Dx0v]\color{#348FEA}{\big[D_{x_0} \langle u, v\rangle\big]} = \langle\color{#348FEA}{\big[D_{x_0} u\big]}, v\rangle + \langle u, \color{#348FEA}{\big[D_{x_0} v\big]}\rangle

В этом нетрудно убедиться, повторив доказательство или заметив, что в доказательстве мы пользовались лишь дистрибутивностью (= билинейностью) умножения.

  1. Производная сложной функции. Пусть f(x)=u(v(x))f(x) = u(v(x)). Тогда

    f(x0+h)f(x0)=u(v(x0+h))u(v(x0))f(x_0 + h) - f(x_0) = u(v(x_0 + h)) - u(v(x_0)) \approx

    [Dv(x0)u](v(x0+h)v(x0))[Dv(x0)u]([Dx0v](h))\approx\left[D_{v(x_0)} u \right] (v(x_0 + h) - v(x_0)) \approx \left[D_{v(x_0)} u \right] \left( \left[D_{x_0} v\right] (h)\right)

    Здесь Dv(x0)uD_{v(x_0)} u — дифференциал uu в точке v(x0)v(x_0), а [Dv(x0)u]()\left[D_{v(x_0)} u \right]\left(\ldots\right) — это применение отображения [Dv(x0)u]\left[D_{v(x_0)} u \right] к тому, что в скобках. Итого получаем:

    [Dx0uv](h)=[Dv(x0)u]([Dx0v](h))\left[D_{x_0} \color{#5002A7}{u} \circ \color{#4CB9C0}{v} \right](h) = \color{#5002A7}{\left[D_{v(x_0)} u \right]} \left( \color{#4CB9C0}{\left[D_{x_0} v\right]} (h)\right)

  2. Важный частный случай: дифференцирование перестановочно с линейным отображением. Пусть f(x)=L(v(x))f(x) = L(v(x)), где LL — линейное отображение. Тогда [Dv(x0)L]\left[D_{v(x_0)} L \right] совпадает с самим LL и формула упрощается:

    [Dx0Lv](h)=L([Dx0v](h))\left[D_{x_0} \color{#5002A7}{L} \circ \color{#4CB9C0}{v} \right](h) = \color{#5002A7}{L} \left( \color{#4CB9C0}{\left[D_{x_0} v\right]} (h)\right)

Простые примеры вычисления производной

  • Вычислим дифференциал и градиент функции f(x)=a,xf(x) = \langle a, x\rangle, где xx — вектор-столбец, aa — постоянный вектор.
Попробуйте вычислить сами, прежде чем смотреть решение.

Вычислить производную можно непосредственно:

f(x0+h)f(x0)=a,x0+ha,x0=a,hf(x_0 + h) - f(x_0) = \langle a, x_0 + h\rangle - \langle a, x_0\rangle = \langle a, h\rangle

Но можно и воспользоваться формулой дифференциала произведения:

[Dx0a,x](h)=\color{#348FEA}{\big[D_{x_0} \langle a, x\rangle\big]} (h) =

=[Dx0a](h),x+a,[Dx0x](h)=\langle\color{#348FEA}{\big[D_{x_0} a\big]}(h), x\rangle + \langle a, \color{#348FEA}{\big[D_{x_0} x\big]}(h)\rangle

=0,x+a,h=a,h= \langle 0, x\rangle + \langle a, h\rangle = \langle a, h\rangle

Сразу видно, что градиент функции равен aa.

  • Вычислим производную и градиент f(x)=Ax,xf(x) = \langle Ax, x\rangle, где xx — вектор-столбец, AA — постоянная матрица.
Попробуйте вычислить сами, прежде чем смотреть решение.

Снова воспользуемся формулой дифференциала произведения:

[Dx0Ax,x](h)=\color{#348FEA}{\big[D_{x_0} \langle Ax, x\rangle\big]}(h) =

=[Dx0Ax](h),x0+Ax0,[Dx0x](h)= \langle\color{#348FEA}{\big[D_{x_0} Ax\big]}(h), x_0\rangle + \langle Ax_0, \color{#348FEA}{\big[D_{x_0} x\big]}(h)\rangle

=Ah,x0+Ax0,h= \langle Ah, x_0\rangle + \langle Ax_0, h\rangle

Чтобы найти градиент, нам надо это выражение представить в виде ?,h\langle ?, h\rangle. Для этого поменяем местами множители первого произведения и перенесём AA в другую сторону (AA перенесётся с транспонированием):

ATx0,h+Ax0,h=\langle A^Tx_0, h\rangle + \langle Ax_0, h\rangle =

=(AT+A)x0,h= \langle (A^T + A)x_0, h\rangle

Получается, что градиент в точке x0x_0 равен (AT+A)x0(A^T + A)x_0.

  • Вычислим производную обратной матрицы: f(X)=X1f(X) = X^{-1}, где XX — квадратная матрица.
Попробуйте вычислить сами, прежде чем смотреть решение.

Рассмотрим равенство I=XX1=II = X\cdot X^{-1} = I и продифференцируем его:

0=[DX0(XX1)](H)=0 = \color{#348FEA}{\big[D_{X_0} \left( X\cdot X^{-1}\right)\big]}(H) =

=[DX0X](H)X01+X0[DX0X1](H)= \color{#348FEA}{\big[D_{X_0} X\big]}(H)\cdot X_0^{-1} + X_0\cdot \color{#348FEA}{\big[D_{X_0} X^{-1}\big]}(H)

Отсюда уже легко выражается

[DX0X1](H)=X01[DX0X](H)X01\color{#348FEA}{\big[D_{X_0} X^{-1}\big]}(H) = -X_0^{-1}\cdot\color{#348FEA}{\big[D_{X_0} X\big]}(H)\cdot X_0^{-1}

Осталось подставить [DX0X](H)=H\color{#348FEA}{\big[D_{X_0} X\big]}(H) = H, но запомните и предыдущую формулу, она нам пригодится.

  • Вычислим градиент определителя: f(X)=det(X)f(X) = \text{det}(X), где XX — квадратная матрица.
Попробуйте вычислить сами, прежде чем смотреть решение.

В предыдущих примерах мы изо всех сил старались не писать матричных элементов, но сейчас, увы, придётся. Градиент функции состоит из её частных производных: x0f=(fxij)i,j\color{#FFC100}{\nabla_{x_0} f} = \left(\frac{\partial f}{\partial{x_{ij}}}\right)_{i,j}. Попробуем вычислить fxij\frac{\partial f}{\partial{x_{ij}}}. Для этого разложим определитель по ii-й строке:

det(X)=kxik(1)i+kMik,\text{det}(X) = \sum_{k}x_{ik}\cdot(-1)^{i + k}M_{ik},

где MikM_{ik} — это определитель подматрицы, полученной из исходной выбрасыванием ii-й строки и kk-го столбца. Теперь мы видим, что определитель линеен по переменной xijx_{ij}, причём коэффициент при ней равен (1)i+kMik\cdot(-1)^{i + k}M_{ik}. Таким образом,

fxij=(1)i+kMik\frac{\partial f}{\partial{x_{ij}}} = (-1)^{i + k}M_{ik}

Чтобы записать матрицу, составленную из таких определителей, покороче, вспомним, что

X1=1det(X)((1)i+jMji)i,jX^{-1} = \frac1{\text{det}(X)}\left((-1)^{i+j}M_{\color{red}{ji}}\right)_{i,j}

Обратите внимание на переставленные индексы ii и jj (отмечены красным). Но всё равно похоже! Получается, что

x0f=det(X)XT,\color{#FFC100}{\nabla_{x_0} f} = \text{det}(X)\cdot X^{-T},

где XTX^{-T} — это более короткая запись для (X1)T(X^{-1})^T.

  • Вычислим градиент функции f(x)=Axb2f(x) = \vert\vert Ax - b\vert\vert^2. С этой функцией мы ещё встретимся, когда будем обсуждать задачу линейной регрессии.
Попробуйте вычислить сами, прежде чем смотреть решение.

Распишем квадрат модуля в виде скалярного произведения:

Axb2=Axb,Axb\vert\vert Ax - b\vert\vert^2 = \langle Ax - b, Ax - b\rangle

Применим формулу дифференциала произведения и воспользуемся симметричностью скалярного произведения:

[Dx0Axb,Axb](h)=\color{#348FEA}{\big[D_{x_0} \langle Ax - b, Ax - b\rangle\big]}(h) =

[Dx0(Axb)](h),Ax0b+Ax0b,[Dx0(Axb)](h)\langle \color{#348FEA}{\big[D_{x_0} (Ax - b)\big]}(h), Ax_0 - b\rangle + \langle Ax_0 - b, \color{#348FEA}{\big[D_{x_0} (Ax - b)\big]}(h)\rangle

=2Ax0b,[Dx0(Axb)](h)== 2\langle Ax_0 - b, \color{#348FEA}{\big[D_{x_0} (Ax - b)\big]}(h)\rangle =

=2Ax0b,Ah=2AT(Ax0b),h= 2\langle Ax_0 - b, Ah\rangle = \langle 2A^T(Ax_0 - b), h\rangle

Получаем, что

x0f=2AT(Ax0b)\color{#FFC100}{\nabla_{x_0} f} = 2A^T(Ax_0 - b)

Примеры вычисления производных сложных функций

  • Вычислим градиент функции f(X)=log(det(X))f(X) = \text{log}(\text{det}(X)).
Попробуйте вычислить сами, прежде чем смотреть решение.

Вспомним формулу производной сложной функции:

[DX0uv](H)=[Dv(X0)u]([DX0v](H))\left[D_{X_0} u \circ v \right](H) = \left[D_{v(X_0)} u \right] \left( \left[D_{X_0} v\right] (H)\right)

и посмотрим, как её тут можно применить. В роли функции uu у нас логарифм:

u(y)=log(u),[Dy0u](s)=1y0s,u(y) = \text{log}(u),\quad \left[D_{y_0} u\right](s) = \frac1y_0\cdot s,

а в роли vv — определитель:

v(X)=det(X),[Dy0v](H)=det(X0)X0T,H,v(X) = \text{det}(X),\quad \left[D_{y_0} v\right](H) = \langle \text{det}(X_0)\cdot X_0^{-T}, H\rangle,

где под скалярным произведением двух матриц понимается, как обычно,

A,B=i,jaijbij=tr(ATB)\langle A, B\rangle = \sum_{i,j}a_{ij}b_{ij} = \text{tr}(A^TB)

Подставим это всё в формулу произведения сложной функции:

[DX0uv](H)=1det(X)det(X)XT,H=\left[D_{X_0} u \circ v \right](H) = \frac1{\text{det}(X)}\cdot\langle \text{det}(X)\cdot X^{-T}, H\rangle =

=1det(X)det(X)XT,H=X0T,H= \langle \frac1{\text{det}(X)}\cdot\text{det}(X)\cdot X^{-T}, H\rangle = \langle X_0^{-T}, H\rangle

Отсюда сразу видим, что

X0f=X0T\color{#FFC100}{\nabla_{X_0} f} = X_0^{-T}

  • Вычислим градиент функции f(X)=tr(AXTX)f(X) = \text{tr}(AX^TX).
Попробуйте вычислить сами, прежде чем смотреть решение.

Воспользуемся тем, что след — это линейное отображение (и значит, перестановочно с дифференцированием), а также правилом дифференцирования сложной функции:

[DX0f](H)=tr([DX0AXTX](H))=\left[D_{X_0} f \right](H) = \text{tr}\left(\left[D_{X_0} AX^TX \right](H)\right) =

=tr(A[DX0XT](H)X0+AX0T[DX0X](H))==\text{tr}\left(A\cdot\left[D_{X_0} X^T \right](H)\cdot X_0 + AX_0^T\left[D_{X_0} X \right](H)\right) =

=tr(AHTX0+AX0TH)=\text{tr}\left(AH^TX_0 + AX_0^TH\right)

Чтобы найти градиент, мы должны представить это выражение в виде ?,H\langle ?, H\rangle, что в случае матриц переписывается, как мы уже хорошо знаем, в виде tr(?TH)=tr(?HT)\text{tr}(?^T\cdot H) = \text{tr}(?\cdot H^T). Воспользуемся тем, что под знаком следа можно транспонировать и переставлять множители по циклу:

=tr(AHTX0)+tr(AX0TH)=\ldots=\text{tr}\left(AH^TX_0\right) + \text{tr}\left(AX_0^TH\right) =

=tr(X0AHT)+tr(HTX0AT)==\text{tr}\left(X_0AH^T\right) + \text{tr}\left(H^TX_0A^T\right) =

=tr(X0AHT)+tr(X0ATHT)==\text{tr}\left(X_0AH^T\right) + \text{tr}\left(X_0A^TH^T\right) =

=tr((X0A+X0AT)HT)=\text{tr}\left((X_0A + X_0A^T)H^T\right)

Стало быть,

X0f=X0A+X0AT\color{#FFC100}{\nabla_{X_0} f} = X_0A + X_0A^T

  • Вычислим градиент функции f(X)=det(AX1B)f(X) = \text{det}\left(AX^{-1}B\right).
Подумайте, почему мы не можем расписать определитель в виде произведения определителей

Расписать у нас может не получиться из-за того, что AA и BB могут быть не квадратными, и тогда у них нет определителей и представить исходный определитель в виде произведения невозможно.

Воспользуемся правилом дифференцирования сложной функции для u(Y)=det(Y)u(Y) = \text{det}(Y), v(X)=AX1Bv(X) = AX^{-1}B. А для этого сначала вспомним, какие дифференциалы у них самих. С функцией uu всё просто:

[DY0u](S)=det(Y0)Y0T,S=\left[D_{Y_0} u\right](S) = \langle \text{det}(Y_0)Y_0^{-T}, S\rangle =

=tr(det(Y0)Y01S)= \text{tr}\left(\text{det}(Y_0)Y_0^{-1}S\right)

Функция vv сама является сложной, но, к счастью, множители AA и BB выносятся из-под знака дифференциала, а дифференцировать обратную матрицу мы уже умеем:

[DX0v](H)=AX01HX01B\left[D_{X_0} v\right](H) = - AX_0^{-1}HX_0^{-1} B

С учётом этого получаем:

[DX0f](H)=[Dv(X0)u]([DX0v](H))=\left[D_{X_0} f \right](H) = \left[D_{v(X_0)} u \right] \left( \left[D_{X_0} v\right] (H)\right) =

=tr(det(AX01B)(AX01B)1(AX01HX01B))=\text{tr}\left(\text{det}(AX_0^{-1}B)(AX_0^{-1}B)^{-1}\left(- AX_0^{-1}HX_0^{-1} B\right)\right)

=tr(det(AX01B)(AX01B)1AX01HX01B)=\text{tr}\left(-\text{det}(AX_0^{-1}B)(AX_0^{-1}B)^{-1}AX_0^{-1}HX_0^{-1} B\right)

Чтобы найти градиент, мы должны, как обычно, представить это выражение в виде tr(?TH)\text{tr}(?^T\cdot H).

=tr(det(AX01B)X01B(AX01B)1AX01H)\ldots=\text{tr}\left(-\text{det}(AX_0^{-1}B)X_0^{-1} B(AX_0^{-1}B)^{-1}AX_0^{-1}H\right)

Стало быть,

X0f=(det(AX01B)X01B(AX01B)1AX01)T={\nabla_{X_0} f} = \left(-\text{det}(AX_0^{-1}B)X_0^{-1} B(AX_0^{-1}B)^{-1}AX_0^{-1}\right)^T =

=det(AX01B)X0TAT(AX01B)TBTX0T=-\text{det}(AX_0^{-1}B)X_0^{-T} A^T(AX_0^{-1}B)^{-T}B^TX_0^{-T}

Вторая производная

Рассмотрим теперь не первые два, а первые три члена ряда Тейлора:

f(x0+h)=f(x0)+[Dx0f](h)+12[Dx02f](h,h)+oˉˉ(h2),f(x_0 + h) = f(x_0) + \color{#348FEA}{\left[D_{x_0} f \right]} (h) + \frac12\color{#4CB9C0}{\left[D_{x_0}^2 f \right]} (h, h) + \bar{\bar{o}} \left(\left|\left| h\right|\right|^2\right),

где [Dx02f](h,h)\color{#4CB9C0}{\left[D_{x_0}^2 f \right]} (h, h) — второй дифференциал, квадратичная форма, в которую мы объединили все члены второй степени.

Вопрос на подумать. Докажите, что второй дифференциал является дифференциалом первого, то есть

[Dx0[Dx0f](h1)](h2)=[Dx02f](h1,h2)\left[D_{x_0} \color{#348FEA}{\left[D_{x_0} f \right]} (h_1) \right] (h_2) = \left[D_{x_0}^2 f \right] (h_1, h_2)

Зависит ли выражение справа от порядка h1h_1 и h2h_2?

Этот факт позволяет вычислять второй дифференциал не с помощью приращений, а повторным дифференцированием производной.

Вторая производная может оказаться полезной при реализации методов второго порядка или же для проверки того, является ли критическая точка (то есть точка, в которой градиент обращается в ноль) точкой минимума или точкой максимума. Напомним, что квадратичная форма q(h)q(h) называется положительно определённой (соответственно, отрицательно определённой), если q(h)0q(h) \geqslant 0 (соответственно, q(h)0q(h) \leqslant 0) для всех hh, причём q(h)=0q(h) = 0 только при h=0h = 0.

Теорема. Пусть функция f:RmRf:\mathbb{R}^m\rightarrow\mathbb{R} имеет непрерывные частные производные второго порядка 2fxixj\frac{\partial^2 f}{\partial x_i\partial x_j} в окрестности точки x0x_0, причём x0f=0\color{#FFC100}{\nabla_{x_0} f} = 0. Тогда точка x0x_0 является точкой минимума функции, если квадратичная форма Dx02f\color{#348FEA}{D_{x_0}^2 f} положительно определена, и точкой максимума, если она отрицательно определена.

Если мы смогли записать матрицу квадратичной формы второго дифференциала, то мы можем проверить её на положительную или отрицательную определённость с помощью критерия Сильвестра.

Примеры вычисления и использования второй производной

  • Рассмотрим задачу минимизации f(x)=Axb2f(x) = \vert\vert Ax - b\vert\vert^2 по переменной xx, где AA — матрица с линейно независимыми столбцами. Выше мы уже нашли градиент этой функции; он был равен x0f=2AT(Axb)\color{#FFC100}{\nabla_{x_0} f} = 2A^T(Ax - b). Мы можем заподозрить, что минимум достигается в точке, где градиент обращается в ноль: x=(ATA)1ATbx_* = (A^TA)^{-1}A^Tb. Отметим, что обратная матрица существует, так как rk(ATA)=rkA\text{rk}(A^TA) = \text{rk}{A}, а столбцы AA по условию линейно независимы и, следовательно, rk(ATA)\text{rk}(A^TA) равен размеру этой матрицы. Но действительно ли эта точка является точкой минимума? Давайте оставим в стороне другие соображения (например, геометрические, о которых мы упомянем в параграфе про линейные модели) и проверим аналитически. Для этого мы должны вычислить второй дифференциал функции f(x)=Axb2f(x) = \vert\vert Ax - b\vert\vert^2.
Попробуйте вычислить сами, прежде чем смотреть решение.

Вспомним, что

[Dx0Axb2](h1)=2AT(Ax0b),h1\color{#348FEA}{\big[D_{x_0} \vert\vert Ax - b\vert\vert^2\big]}(h_1) = \langle 2A^T(Ax_0 - b), h_1\rangle

Продифференцируем снова. Скалярное произведение — это линейная функция, поэтому можно занести дифференцирование внутрь:

[Dx02AT(Axb),h1](h2)=[Dx0(2ATAx2ATb)](h2),h1=\color{#348FEA}{\big[D_{x_0} \langle 2A^T(Ax - b), h_1\rangle\big]}(h_2) = \langle \color{#348FEA}{\big[D_{x_0} (2A^TAx - 2A^Tb)\big]}(h_2), h_1\rangle =

=2ATAh2,h1=2h2TATAh1=\langle 2A^TAh_2, h_1\rangle = 2h_2^T A^TA h_1

Мы нашли квадратичную форму второго дифференциала; она, оказывается, не зависит от точки (впрочем, логично: исходная функция была второй степени по xx, так что вторая производная должна быть константой). Чтобы показать, что xx_* действительно является точкой минимума, достаточно проверить, что эта квадратичная форма положительно определена.

Попробуйте сделать это сами, прежде чем смотреть решение.

Хорошо знакомый с линейной алгеброй читатель сразу скажет, что матрица ATAA^TA положительно определена для матрицы AA с линейно независимыми столбцами. Но всё же давайте докажем это явно. Имеем hTATAh=(Ah)TAh=Ah20h^TA^TAh = (Ah)^TAh = \vert\vert Ah\vert\vert^2 \geqslant 0. Это выражение равно нулю тогда и только тогда, когда Ah=0Ah = 0. Последнее является однородной системой уравнений на hh, ранг которой равен числу переменных, так что она имеет лишь нулевое решение h=0h = 0.

  • Докажем, что функция f(X)=logdet(X)f(X) = \log{\text{det}(X)} является выпуклой вверх на множестве симметричных, положительно определённых матриц. Для этого мы должны проверить, что в любой точке квадратичная форма её дифференциала отрицательно определена. Для начала вычислим эту квадратичную форму.
Попробуйте сделать это сами, прежде чем смотреть решение.

Выше мы уже нашли дифференциал этой функции:

[DX0logdet(X)](H1)=X0T,H1\color{#348FEA}{\big[D_{X_0} \log{\text{det}(X)}\big]}(H_1) = \langle X_0^{-T}, H_1\rangle

Продифференцируем снова:

[DX0XT,H1](H2)=[Dx0XT](H2),h1=\color{#348FEA}{\big[D_{X_0} \langle X^{-T}, H_1\rangle\big]}(H_2) = \langle \color{#348FEA}{\big[D_{x_0} X^{-T}\big]}(H_2), h_1\rangle =

=X01H2X01,H1=\langle -X_0^{-1}H_2X_0^{-1}, H_1\rangle

Чтобы доказать требуемое в условии, мы должны проверить следующее: что для любой симметричной матрицы X0X_0 и для любого симметричного (чтобы не выйти из пространства симметричных матриц) приращения H0H\ne 0 имеем

[DX02logdet(X)](H,H)<0\color{#348FEA}{\big[D^2_{X_0} \log{\text{det}(X)}\big]}(H, H) < 0

Покажем это явно.
Так как X0X_0 — симметричная, положительно определённая матрица, у неё есть симметричный и положительно определённый квадратный корень: X0=X01/2X01/2=X01/2(X01/2)T.X_0 = X_0^{1/2}\cdot X_0^{1/2} = X_0^{1/2}\cdot \left(X_0^{1/2}\right)^T. Тогда

X01HX01,H=tr(X01/2(X01/2)THX01/2(X01/2)THT)=\langle -X_0^{-1}HX_0^{-1}, H\rangle = -\text{tr}\left(X_0^{1/2} \left(X_0^{1/2}\right)^THX_0^{1/2} \left(X_0^{1/2}\right)^TH^T\right) =

tr((X01/2)THX01/2(X01/2)THTX01/2)=-\text{tr}\left(\left(X_0^{1/2}\right)^THX_0^{1/2} \left(X_0^{1/2}\right)^TH^TX_0^{1/2}\right) =

=tr((X01/2)THX01/2[(X01/2)THX01/2]T)==-\text{tr}\left( \left(X_0^{1/2}\right)^THX_0^{1/2} \left[\left(X_0^{1/2}\right)^THX_0^{1/2}\right]^T\right) =

=(X01/2)THX01/22,=-\vert\vert\left(X_0^{1/2}\right)^THX_0^{1/2}\vert\vert^2,

что, конечно, меньше нуля для любой ненулевой HH.

Чтобы добавить в заметки выделенный текст, нажмите Command + E

Пройдите квиз по параграфу

Чтобы закрепить пройденный материал
Предыдущий параграф15.4. Методы оптимизации в Deep Learning
Следующий параграф16.2. Матричная факторизация

Вступайте в сообщество хендбука

Здесь можно найти единомышленников, экспертов и просто интересных собеседников. А ещё — получить помощь или поделиться знаниями.